/*
 * @Author: xiguan
 * @Email: xiguan.teng@qq.com
 * @Version: 1.0
 * @Date: 2022-09-15 09:21:29
 * @LastEditTime: 2022-09-21 09:40:32
 */
#include <bits/stdc++.h>
#include <stdlib.h>

using namespace std;
typedef long long ll;

typedef struct treeNode{
    int data;
    struct treeNode *left_child;
    struct treeNode *right_child;

    treeNode( int x ) : data(x), left_child(nullptr), right_child(nullptr) {};
    treeNode( int x, treeNode *l, treeNode *r ) : data(x), left_child(l), right_child(r) {};
}treeNode, *treeNodePtr;

void treePreOrder( treeNodePtr root ){
    if( root == nullptr ){
        return ;
    }

    cout << root->data << " ";
    treePreOrder( root->left_child );
    treePreOrder( root->right_child );
}

void treeInOrder( treeNodePtr root ){
    if( root == nullptr ){
        return ;
    }
    treeInOrder( root->left_child );
    cout << root->data << " ";
    treeInOrder( root->right_child );
}

void treePosOrder( treeNodePtr root ){
    if( root == nullptr ){
        return ;
    }
    treePosOrder( root->left_child );
    treePosOrder( root->right_child );
    cout << root->data << " ";
}

void treePreOrderUnRecur( treeNodePtr head ){
    cout << "pre-order : " << endl;
    if( head != nullptr ){
        stack<treeNodePtr> s;
        s.push( head );

        while( !s.empty() ){
            head = s.top();
            s.pop();
            cout << head->data << " ";
            if( head->left_child != nullptr ){
                s.push( head->left_child );
            }
            if( head->right_child != nullptr ){
                s.push( head->right_child );
            }
        }
    }
    cout << endl;
}

void treeInOrderUnRecur( treeNodePtr head ){
    cout << "in-order : " << endl;
    if( head != nullptr ){
        stack<treeNodePtr> s;
        while( !s.empty() || head != nullptr ){
            if( head != nullptr ){
                s.push( head );
                head = head->left_child;
            }else{
                head = s.top();
                s.pop();
                cout << head->data << " ";
                head = head->right_child;
            }
        }
    }
    cout << endl;
}

void treePosOrderUnRecur( treeNodePtr head ){
    cout << "pos-order : " << endl;
    if( head != nullptr ){
        stack<treeNodePtr> s1, s2;
        s1.push( head );

        while( !s1.empty() ){
            head = s1.top();
            s1.pop();
            s2.push( head );
            if( head->left_child != nullptr ){
                s1.push( head->left_child );
            }
            if( head->right_child != nullptr ){
                s1.push( head->right_child );
            }
        }
        while( !s2.empty() ){
            head = s2.top(); s2.pop();
            cout << head->data << " ";
        }
    }
    cout << endl;
}


int main( int argc, char *argv[] ){

    

    return 0;
}